package com.yangzhe.algorithm.c011;

// 给你两个 非空 的链表，表示两个非负的整数
// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头
// 测试链接：https://leetcode.cn/problems/add-two-numbers/
public class AddTwoNumbers {

    /**
     * Definition for singly-linked list.
     */

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int carry = 0;
            ListNode result = null;
            ListNode resultCur = null;
            for (ListNode cur1 = l1, cur2 = l2;
                 cur1 != null || cur2 != null;
                 cur1 = cur1 == null ? null : cur1.next, cur2 = cur2 == null ? null : cur2.next
            ) {
                int sum = (cur1 == null ? 0 : cur1.val) + (cur2 == null ? 0 : cur2.val) + carry;
                carry = sum / 10;
                ListNode node = new ListNode(sum % 10, null);
                if (result == null) {
                    result = node;
                    resultCur = node;
                } else {
                    resultCur.next = node;
                    resultCur = node;
                }
            }

            if (carry != 0) {
                ListNode end = new ListNode(carry);
                resultCur.next = end;
            }

            return result;
        }
    }
}
